//栈与队列
#include <stdio.h>
#include <stdlib.h>
#define maxSize 100

//顺序栈的定义
typedef struct subsequenceStack
{
	int data[maxSize];
	int top;	//用来定位栈顶
}subsequenceStack;

//链栈结点的定义
typedef struct chainStackNode
{
	int data;
	struct chainStackNode *next;
}chainStackNode;

//顺序队的定义
typedef struct subsequenceQueue
{
	int data[maxSize];
	int front;//用来定位队头
	int rear;
}subsequenceQueue;

//队结点的定义———队的成员，有数据域
typedef  struct queueNode
{
	int data;
	struct queueNode *next;
}queueNode;

//链队头结点的定义--不需要数据，只存两个指针
typedef struct chainQueue
{
	struct queueNode *front;//队头指针
	struct queueNode *rear;//队尾指针
}chainQueue;


int main(int argc, char *argv[]) {
	/*栈的基本概念*/
	//栈————特殊的线性表————特殊性：只可在一端进行插入和删除操作————效果：先录入的数据，只能最后删除（先进后出）
			//顺序栈		//该端称为“栈顶”，插入称为“入栈”，删除称为“出栈”
			//链栈		//另一端称为“栈底”
			
	/*队的基本概念*/
	//队————特殊的线性表————特殊性：只可在一端插入，在另一端删除————效果：先录入的数据，只能最先删除（先进先出）
			//顺序队			//插入的一端称为“队尾”，插入叫做“进队”
			//链队			//删除的一端称为“队头”，删除叫做“出队”
			
	
	//顺序栈的三种状态
	subsequenceStack s;
	s.top = -1;//栈空状态，栈空时继续出栈————下溢———非法状态
				//s.top = 0时，仍然会占用一个空间，仍可以存储一个元素
				//不同的书，对栈空的定义不同
	s.top = maxSize-1;//栈满状态，栈满时继续入栈————上溢————非法状态
	
	//链栈的特殊状态————栈空状态
	chainStackNode ls;
	ls.next = NULL;
	
}


/*****顺序栈的基本操作*****/
//元素x的进栈操作————若会上溢，则返回0
int subsequenceStackPush(subsequenceStack *s,int x)
{
	//判断是否会上溢
	if(s->top == maxSize -1)
		return 0;
	//进栈
	s->top++;
	s->data[s->top] = x;
	//等价于： s->data[++s->top] = x;
	return 1;
}

//栈顶元素的出栈操作————为防止数据丢失，用x记录栈顶元素————若会下溢，则返回0
int subsequenceStackPop(subsequenceStack *s,int x)
{
	//判断是否会下溢
	if(s->top == -1)
		return 0;
	//出栈
	x = s->data[s->top];
	s->top--;
	//等价于： x = s->data[s->top--];
	return 1;
}


//顺序栈的应用————给定一个字符数组str[n],判断里面的“("、")"是否全部配对（要求遵守前后顺序）————不配对则返回 0
int match(char str[],int n)
{
	char data[maxSize];
	int top = -1;//定义顺序栈
	
	//遍历str[]————“（”进栈，“）”出栈————看看最后是否为空栈
	for(int i=0;i<n;i++)
	{
		if(str[i]=='(')
			data[++top] = str[i];
		if(str[i]==')')
		{
			--top;
			//出现下溢，则配对不成功
			if(top<-1)
				return 0;
		}
	}
	//判断
	if(top==-1)
		return 1;
	else return 0;
}


/*****链栈的基本操作*****/
//元素x的进栈操作
void chainStackPush(chainStackNode *ls,int x)
{
	//开辟一个空间————存储x
	chainStackNode *p=(chainStackNode *)malloc(sizeof(chainStackNode));
	p->data = x;
	
	//将构造的结点进栈————头插法
	p->next = ls->next;
	ls->next = p;
}


//出栈操作————为防止数据丢失，用x来存储————若为空栈，则返回0
int chainStackPop(chainStackNode *ls,int x)
{
	//判断是否为空栈
	if(ls->next==NULL)
		return 0;
	//存储即将出栈的数据(头结点的后一个结点)，建立新联系，完成出栈操作
	chainStackNode *p;//创造一个指针，用来定位即将释放的结点
	p = ls->next;
	x = p->data;
	ls->next = p->next;
	free(p);
	return 1;
}


/*****顺序栈的运用*****/
//字符数组a[n]中，存有一系列括号“）”、“（”，检验它们是不是两两配对，在意它们前后顺序
int march(char a[],int n)
{
	int stack[maxSize],top=-1;//创建一个空的顺序栈
	
	//'('表示进栈，‘）’表示出栈，看看最后是不是空栈————来判断是不是两两配对
	for(int i=0;i<n;i++)
	{
		if(a[i]=='(')
		{
			top++;
			stack[top]=a[i];
		}
		if(a[i]==')')
		{
			top--;
			if(top==-2)return 0;
		}
	}
	if(top==-1)return 1;
	else return 0;
}

//已知一个后缀表达式，存于一个字符数组exp[]中，求其值
		//思路：遇到数，就存入栈中；遇到运算符，就把栈中的数拿来运算，结果再入栈————周而复始，最终就可以得到结果
int calculate(int a, char op,int b)
{
	if(op=='-') return a-b;
	else if(op=='+') return a+b;
	else if(op=='*') return a*b;
	else return a/b;
}
int result(char exp[])
{
	int stack[maxSize],top = -1;//一句话，创造一个顺序栈
	for(int i=0;exp[i]!='\0';i++)
	{
		//将数字存入栈中
		if(exp[i]>='0'&&exp[i]<='9')
		{
			stack[++top] = exp[i]-'0';
		}
		
		//如果遇到运算符，则开始计算
		else {
			int a,b,c;
			b = stack[top--];
			a = stack[top--];//将栈中的数字拿出
			
			c = calculate(a,stack[i],b);//运算操作
			stack[++top] = c;//结果重新入栈
		}
	}
	return stack[top];
	
}

//中缀转后缀表达式————输入一个中缀表达式，以‘#’为结束标记，输出后缀表达式
int prior(char ch)//判断优先级
{
	switch(ch)
	{
		case'(':case')':return 1;
		case'-':case'+':return 2;
		case'*':case'/':return 3;
		case'^':return 4;
	}
	return 0;
}
void infixToSuffix()
{
	char input[100];//用来接收输入的中缀表达式
	char output[100];int n=-1;//用来存储将要输出的后缀表达式
	char stack[100];int top=-1;//创造一个栈，用来存储运算符————作为过渡的空间
	
	for(int i=0;;i++)
	{
		input[i] = getchar();
		if(input[i]=='#')break;//如果是结束字符，则跳出
		
		else if(input[i]=='(')//直接入栈
		{
			stack[++top] = input[i];
		}
		
		else if(input[i]=='+'||input[i]=='-'||input[i]=='*'||input[i]=='/'||input[i]=='^')
		{
			if(top==-1)//如果是空栈，则直接进入
				stack[++top] = input[i];
			
			//之后要判断运算符的优先级，应用函数prior()
			else if(prior(input[i])>prior(stack[top]))//如果输入的运算符 优先于栈内元素————则进栈
			{
				stack[++top] = input[i];
			}
			
			else if(prior(input[i])<=prior(stack[top]))//如果输入的运算符 劣后于栈内元素————则进栈，并输出所有比其优先的运算符
			{
				while(prior(input[i])<=prior(stack[top]))
					output[++n] = stack[top--];
				stack[++top] = input[i];
			}
		}
		
		else if(input[i]==')')//出栈操作
		{
			while(stack[top]!='(')
			{
				output[++n] = stack[top--];
			}
			top--;
		}
		
		else if(input[i]>='A'&&input[i]<='Z'||input[i]>='a'&&input[i]<='z')//直接输出
		{
			output[++n] = input[i];
		}
	}
	//输出栈内剩余元素
	while(top!=-1)
		{
			output[++n] = stack[top--];
		}

	//最后，做输出操作
	for(int i=0;i<=n;i++)
	{
		printf("%c",output[i]);
	}
}



/*****顺序队的基本操作*****/

//顺序队————如果单纯用数组储存，用front定位队头，用rear定位队尾——则进队rear要后移，出队front要后移，最终就会超过maxSize最大数组空间
		//————优化办法： 创造循环队列，让两个定位点在一个圈内循环——通过（rear｜front+1）%maxSize，在定位点到最后的时候，再返回初始点——就不会超过最大空间了
//循环队列的两种特殊状态————qu.rear==qu.front队空状态————两定位点指向一个地方，默认队头front为空
					//————(qu.rear+1)%maxSize==qu.front队满状态————让rear指向front的前一格————最多存maxSize-1个数据
					
//队中元素个数：(qu.rear-qu.front+maxSize)%maxSize
					
//进队操作————让元素x进队——如果队满，则返回 0
int enterSubsequenceQueue(subsequenceQueue *qu,int x)
{
	//判断是否队满
	if((qu->rear+1)%maxSize==qu->front)
		return 0;
	
	qu->rear = (qu->rear+1)%maxSize;//调整队尾的定位————将定位移到下一位，并保持循环
	qu->data[qu->rear] = x;//进队
	return 1;
}

//出队操作————为防止数据丢失，用x保存————如果队空，则返回 0
int detachSubsequenceQueue(subsequenceQueue *qu,int *x)
{												//x用于存储，因此要将记录值返回
	//判断队列是否为空
	if(qu->rear==qu->front)
		return 0;
	
	qu->front = (qu->front+1)%maxSize;//front定位的是队头，队头记录的是空值————要出队，并记录数据，应该指向其下一位
									//移动front即完成出队
	*x = qu->data[qu->front];//记录好数据
	return 1;
}


/*****链队的基本操作*****/
//创造一个链队
void initiateChainQueue(chainQueue **lqu)
{						//用一个指向头结点的指针，表示整个链队
	*lqu = (chainQueue *)malloc(sizeof(chainQueue));//开辟一个空间，存储链队头结点
	
	(*lqu)->front = (*lqu)->rear = NULL;//让链队为空
}

//入队操作————让元素x入队
void enterChainQueue(chainQueue *lqu,int x)
{
	queueNode *p = (queueNode *)malloc(sizeof(queueNode));//开辟一个队结点空间，用于存储数据
	p->data = x;
	p->next = NULL;
	
	//让新结点入队
	if(lqu->rear == NULL)//如果入的是空队
	{
		lqu->front = p;
		lqu->rear = p;
	}
	else{//如果不是空队
		lqu->rear->next = p;
		lqu->rear = p;
	}
}

//出队操作————从队头中离开————为防止数据丢失，将出队数据存入x中————若为空队，则返回 0
int deleteChainQueue(chainQueue *lqu,int *x)
{
	queueNode *p;//创造一个指针，定位要删除的结点
	if(lqu->front==NULL)//如果链队为空
		return 0;
		
	else if(lqu->front==lqu->rear)//如果链队只有一个成员
	{
		p = lqu->front;
		lqu->front = lqu->rear = NULL;
	}
	
	else{//如果链队有多个成员
		p = lqu->front;
		lqu->front = lqu->front->next;
	}
	
	*x = p->data;//存储数据
	free(p);
	return 1;
}